First Missing Positive

Given an unsorted integer array, find the first missing positive integer.

For example,

Given [1,2,0] return 3,
and [3,4,-1,1] return 2.

Your algorithm should run in O(n) time and uses constant space.

Solution:

  1. public class Solution {
  2.   public int firstMissingPositive(int[] a) {
  3.     int i = 0;
  4.     while (i < a.length) {
  5.       if (a[i] > 0 && a[i] <= a.length && a[i] != a[a[i] - 1]) {
  6.         swap(a, i, a[i] - 1);
  7.       } else {
  8.         i++;
  9.       }
  10.     }
  12.     i = 0;
  13.     while (i < a.length && a[i] == i + 1) {
  14.       i++;
  15.     }
  17.     return i + 1;
  18.   }
  20.   void swap(int[] a, int i, int j) {
  21.     int b = a[i];
  22.     a[i] = a[j];
  23.     a[j] = b;
  24.   }
  25. }